package mid;

public class a面试题01_05_一次编辑 {
    public boolean oneEditAway(String first, String second) {
        if (Math.abs(first.length() - second.length()) > 1) return false;
        if (first.length() > second.length()) return oneEditAway(second, first);
        char[] cs1 = first.toCharArray(), cs2 = second.toCharArray();
        int n = cs1.length, m = cs2.length;
        //长度不同，检查最长公共子序列
        if (n != m) {
            return checkLCS(cs1, n, cs2, m);
        }
        //长度相同，检查不同字符数
        return checkDiff(cs1, cs2, n);
    }

    boolean checkDiff(char[] cs1, char[] cs2, int n) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (cs1[i] != cs2[i]) cnt++;
            if (cnt > 1) return false;
        }
        return true;
    }

    boolean checkLCS(char[] cs1, int n, char[] cs2, int m) {
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (cs1[i - 1] == cs2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i][j - 1], f[i - 1][j]);
                }
            }
        }
        return f[n][m] == m;
    }
}